package com.stefan.linkedlist;

//单向链表的数据结构 + 头插法
public class StefanLinkedList<E> {
    private int size;
    private Node<E> head;

    public StefanLinkedList() {
        head = new Node(null);
    }

    static class Node<E> {
        private E data;
        private Node<E> next;

        public Node(E data) {
            this.data = data;
        }
    }

    public void add(E value) {
        //头插法
        add(0,value);
    }

    public void add(int position,E value) {
        Node<E> node = new Node(value);
        if (position == 0) {
            node.next = this.head;
            this.head = node;
        } else {
            Node<E> var = this.head; // 拿到head然后遍历
            for (int i = 1;i < position;i++) {
                var = var.next; //遍历到要插入的位置的node前一个node
            }
            node.next = var.next; //把要插入的node的next指向当前位置
            var.next = node; //
        }
        size++;
    }
    public E remove(int position) {
        if (position > size) {
            throw new IndexOutOfBoundsException();
        }
        if (position == 0) {
            return removeHead();
        } else {
            Node<E> var = this.head;
            for (int i = 1; i < position; i++) {
                var = var.next;
            }
            Node<E> current = var.next;
            var.next = current.next;
            current.next = null;
            size --;
            return current.data;
        }
    }
    private E removeHead() {
        E result = (E)this.head.data;
        this.head = head.next;
        size --;
        return result;
    }

    public E find(int position) {
        if (position > size) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> var = this.head; // 拿到head然后遍历
        for (int i = 0;i < position;i++) {
            var = var.next; //
        }
        return var.data;
    }

    public static void main(String[] args) {
        StefanLinkedList<String> stefanLinkedList = new StefanLinkedList();
        stefanLinkedList.add("1");
        stefanLinkedList.add("2");
        stefanLinkedList.add("3");
        stefanLinkedList.add("4");
        stefanLinkedList.add("5");
        stefanLinkedList.add(5,"9");
        System.out.println("======");
        stefanLinkedList.remove(3);
        stefanLinkedList.find(3);
        System.out.println("======");
    }

}
